www.jeanjoux.fr - Tutoriel match

Le code source de cet exemple peut être téléchargé ici.

Introduction

Comparer des chaînes de caractères est très courant lorsque l'on fait de l'informatique et rapidement un besoin se fait sentir: Comparer des chaînes de caractères avec des différences à certains endroits précis de la chaîne. Par exemple, on peut avoir besoin qu'une chaîne de caractère se termine de plusieurs façons possibles contiennent des sous-chaînes particulière, ou qu'un caractère particulier puissent changer.

La fonction (==) de Haskell ne permet donc plus de faire ces tests.

Une solution pourrait être d'utiliser les expression rationnelles (REGEX) et plusieurs bibliothèque permettent de travailler avec ces expressions ( Text.Regex ou regex-posix ).

Mais cette solution peut s'avérer être lourde à mettre en œuvre, et pour une petite comparaison rapide, cela peut ne pas être pertinent.

Voici donc une petite fonction simple à implémenter avec Haskell ¹ et permettant de faire des comparaisons approximatives simples sur des chaînes de caractères qui peuvent être satisfaisante pour la plupart des cas.

Première version

Implémentation

La fonction prendra comme argument :

Une chaîne de caractère "empreinte" qui contiendra la chaîne à trouver avec le code de recherche
La chaîne de caractère à tester.

La chaîne de caractère empreinte pourra reconnaître :

? comme pouvant contenir un unique caractère quelconque.
* comme pouvant contenir n'importe quelle nombre de caractère quelconque.

Analysons, maintenant les différentes empreintes Haskell

10 :

Si il n'y a plus de caractère à tester dans la chaîne "empreinte" et qu'il n'y en a plus non plus dans la chaîne à tester, La comparaison est réussie

La fonction renvoie True.

20 :

Si il n'y a plus de caractère à tester dans la chaîne "empreinte" mais qu'il en reste dans la chaîne à tester, la comparaison échoue.

La fonction renvoie False.

30 :

Si il ne reste plus qu'un seul caractère * dans la chaîne "empreinte" et qu'il reste des caractère dans la chaîne à tester, le test est réussi.

La fonction renvoie True.

40 :

Si la chaîne à tester est vide est que la chaîne "empreinte" ne contient que des caractères *, le test est réussi.

La fonction renvoie True.

50 :

Si le premier caractère de la chaîne empreinte est un *, on test deux cas possibles :

on saute le caractère * dans l'empreinte et on relance le test avec toute la chaîne à comparer. Cela permet de tester le cas ou le caractère * dans l'empreinte représente une absence de caractère particulier dans la chaîne à comparer.
on conserve le caractère * dans l'empreinte et on relance le test en supprimant le premier élément de la chaîne à comparer. Cela permet de tester le cas ou le caractère * dans l'empreinte représente n'importe quel caractère dans la chaîne à comparer.

60 :

Si le premier caractère de la chaîne empreinte est un ?, on saute ce caractère ainsi que le premier caractère de la chaîne à tester et on relance le teste avec la suite des deux chaînes de caractère.

70 :

On teste le premier caractère de la chaîne "empreinte" et le premier test de la chaîne à comparer.

Si ce premier test échoue, la fonction de termine par un échec².
Si ce premier test réussie³, on relance le teste avec la suite des deux chaînes de caractère.

match :: String -> String -> Bool
match pattern str =  match' pattern str
  where
    -- 10 
    match' [] [] = True

    -- 20
    match' [] _ = False

    -- 30 
    match' ['*'] s = True

    -- 40
    match' pat [] = all (== '*') pat

    -- 50
    match' ('*':ps) s = match' ps s || match' ('*':ps) (tail s)

    -- 60
    match' ('?':ps) (c:cs) = match' ps cs

    -- 70
    match' (p:ps) (c:cs) = p == c && match' ps cs

Test

On effectue quelques tests pour vérifier que tout fonctionne bien.

Tout marche comme prévu.

Première amélioration

Implémentation

Cette première implémentation a cependant un petit problème. Si on veut comparer des chaînes contenant des astérisques * et des point d'interrogation ? à certains endroits précis, les empreintes actuelle ne pourront pas les repérer.

Pour pouvoir correspondre à un caractère * ou ? particulier, il faudra le faire précéder d'un caractère \⁴.

De même, il faut envisager le cas ou on veut positionner un caractère \ a un endroit précis dans la chaîne à comparer.

Il faudra donc créer des empreintes Haskell spécifiques dans la fonction pour pouvoir les repérer. Ce sera le rôle des empreintes 51,61 et 65 :

51 :: Si les premiers caractères de la chaîne empreinte sont \* et que le premier caractère de la chaîne à comparer est *, on supprime ces caractères et on relance le test.
61 :: Si les premiers caractères de la chaîne empreinte sont \? et que le premier caractère de la chaîne à comparer est ?, on supprime ces caractères et on relance le test.
65 :: Si les premiers caractères de la chaîne empreinte sont \\ et que le premier caractère de la chaîne à comparer est \, on supprime ces caractères et on relance le test.

match :: String -> String -> Bool
match pattern str =  match' pattern str
  where
    -- 10 
    match' [] [] = True

    -- 20
    match' [] _ = False

    -- 30 
    match' ['*'] s = True

    -- 40
    match' pat [] = all (== '*') pat

    -- 50
    match' ('*':ps) s = match' ps s || match' ('*':ps) (tail s)

    -- 51
    match' ('\\':'*':ps) ('*':cs) = match' ps cs

    -- 60
    match' ('?':ps) (c:cs) = match' ps cs

    -- 61
    match' ('\\':'?':ps) ('?':cs) = match' ps cs

    -- 65
    match' ('\\':'\\':ps) ('\\':cs) = match' ps cs

    -- 70
    match' (p:ps) (c:cs) = p == c && match' ps cs

Test

On test:

Tout marche bien !

Deuxième amélioration

Implémentation

On peut maintenant comparer n'importe quelle chaîne de caractère avec une empreinte décrivant les différentes variantes de cette chaîne. Mais il reste un point que l'on pourrait traiter. Le cas ou on veuille tester plusieurs empreintes sur une chaîne et retenir une chaîne si elle répond aux critères données pas une empreinte.

Pour cela, il faudrait définir un séparateur permettant de définir plusieurs empreintes dans un même chaîne de caractère. Souvent, le caractère | sert à représenter l'opérateur OU, il serait donc pertinent d'utiliser ce caractère pour séparer les empreintes.

Mais attention, ce séparateur pourrait aussi être un caractère à comparer ! Il faut donc également envisager le même cas que précédemment.

If faut donc créer une fonction qui découpe une chaîne de caractère en plusieurs à chaque caractère | qui n'est pas précédé d'un \

On implémente la fonction splitAtChar' qui réalisera cette opération :

La fonction interne go permet de lancer l'analyse de la chaîne de caractère avec un accumulateur :

10 :

Cette empreinte renvoi le contenu de l'accumulateur (inversé) si la chaîne est vide.

20 :

Cette empreinte détecte le cas ou la chaîne commence par un caractère \. C'est le cas ou le caractère délimiteur sera "échappé" et donc, la chaîne ne sera pas découpée.

30 :

Cette empreinte détecte les autres cas. C'est le cas ou le caractère délimiteur sera bien interpréta comme tel et donc, la chaîne sera coupée a cet endroit.

Si le caractère en début de chaîne est le caractère délimiteur, on créé un nouvel élément dans la liste de sortie avec le contenu (inversé) de l'accumulateur et on relance la fonction go avec le reste de la chaîne et l'accumulateur vide.
Si le caractère en début de chaîne n'est pas le caractère délimiteur, on continu l'analyse de la chaîne d'entrée.

splitAtChar' :: Char -> String -> [String]
splitAtChar' _ [] = []
splitAtChar' delimiter str = go str []
  where
    go [] acc = [reverse acc]      -- 10
    go ('\\':x:xs) acc             -- 20 
      | x == delimiter = go xs (x:acc)
      | otherwise      = go (x:xs)  ('\\':acc)
    go (x:xs) acc                  -- 30
      | x == delimiter = reverse acc : go xs []
      | otherwise      = go xs (x:acc)

Il ne reste plus qu'a inclure cette fonction dans la fonction principale. On utilise la fonction any pour tester chaque empreinte avec match' et renvoyer True dès que la première empreinte sera validée.

match :: String -> String -> Bool
match pattern str =  any  (\p -> match' p str ) (splitAtChar' '|' pattern)
  where
    -- 10 
    match' [] [] = True

    -- 20
    match' [] _ = False

    -- 30 
    match' ['*'] s = True

    -- 40
    match' pat [] = all (== '*') pat

    -- 50
    match' ('*':ps) s = match' ps s || match' ('*':ps) (tail s)

    -- 51
    match' ('\\':'*':ps) ('*':cs) = match' ps cs

    -- 60
    match' ('?':ps) (c:cs) = match' ps cs

    -- 61
    match' ('\\':'?':ps) ('?':cs) = match' ps cs

    -- 65
    match' ('\\':'\\':ps) ('\\':cs) = match' ps cs

    -- 70
    match' (p:ps) (c:cs) = p == c && match' ps cs


splitAtChar' :: Char -> String -> [String]
splitAtChar' _ [] = []
splitAtChar' delimiter str = go str []
  where
    go [] acc = [reverse acc]
    go ('\\':x:xs) acc
      | x == delimiter = go xs (x:acc)
      | otherwise      = go (x:xs)  ('\\':acc)
    go (x:xs) acc
      | x == delimiter = reverse acc : go xs []
      | otherwise      = go xs (x:acc)

Test

On test à nouveau :

Tout est bon !

Conclusion

Cette petite fonction m'a déjà été fort utile dans certains de mes programmes pour chercher et filtrer des noms avec des motifs spécifiques.

J'espère qu'elle vous sera également utile.

Ci dessous, le diagramme de fonctionnement de la fonction:

Notes

1.↑	ou tout autre langage de programmation
2.↑	Dans le cas ou on souhaiterais faire un test sans prendre en considération la casse des caractères, il faudra modifier ce premier test et utiliser les fonctions `toUpper` pour mettre les deux caractères en majuscule.
3.↑	L'implémentation de l'opérateur `(&&)` et l'évaluation paresseuse de Haskell font que si le premier membre de l'opérateur est à l'état `False`, le deuxième membre de l'opérateur `(&&)` ne sera pas évalué. Ceci n'est pas forcément vrai avec d'autres langages de programmation ou il faudra faire le premier test de façon séparée.
4.↑	en réalité il en faudra 2 car le caractère d'échappement `\` de chaîne est également le caractère d'échappement des chaînes de caractères Haskell.

Tutoriel Match

Tutoriel match

Introduction

Première version

Implémentation

Test

Première amélioration

Implémentation

Test

Deuxième amélioration

Implémentation

Test

Conclusion